#include <iostream>
#include <stdlib.h>

#define MaxSize 5
typedef int ElemType;
typedef struct LinkNode
{
    ElemType data;
    struct LinkNode* next;
}LinkNode;

typedef struct {
    LinkNode*front,*rear;//链表头，链表尾
}LinkQueue;//先进先出

//队列的初始化，使用的是带头节点的链表来实现的
void InitQueue(LinkQueue& Q)
{
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
//入队
void EnQueue(LinkQueue& Q, ElemType x)
{
    LinkNode *pnew=(LinkNode*)malloc(sizeof(LinkNode));
    pnew->data=x;
    pnew->next=NULL;//要让next为NULL
    Q.rear->next=pnew;//尾指针的next指向pnew,因为从尾部入队
    Q.rear=pnew;//rear要指向新的尾部
}

//出队
bool DeQueue(LinkQueue& Q, ElemType& x)
{
    if(Q.rear==Q.front)//队列为空
    {
        return false;
    }
    LinkNode* del = Q.front->next;//拿到第一个节点，存入q
   x=del->data;//获取要出队的元素值
    Q.front->next=del->next;//让第一个节点断链
    if(Q.rear==del)//链表只剩余一个节点，被删除后，要改变rear
    {
        Q.rear=Q.front;
    }
    free(del);
    return true;
}

//通过链表实现队列
int main()
{
    LinkQueue Q;
    bool ret;
    ElemType element;
    InitQueue(Q);//初始化队列
    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);
    ret=DeQueue(Q,element);
    if(ret)
    {
        printf("DeQueue success, the element is %d\n", element);

    }
    else
    {
        printf("DeQueue fail\n");
    }
    ret=DeQueue(Q,element);
    if(ret)
    {
        printf("DeQueue success, the element is %d\n", element);

    }
    else
    {
        printf("DeQueue fail\n");
    }
    return 0;
}


